Random number generation is utilized in a variety of technologies, such as cryptographic systems, electronic gaming devices, smart card authentication devices, and audio/video scrambling devices. In cryptographic systems, symmetric ciphers, such as the data encryption standard (DES), require a randomly selected encryption key. Public-key algorithms like Rivest Shamir Adelman (RSA), Diffie-Hellman, and Digital Signature Algorithm (DSA) require randomly generated key pairs. Furthermore, the secure sockets layer (SSL) and other cryptographic protocols use random challenges in the authentication process to foil attacks.
Due to the widespread use of random numbers, a random number generator must be robust enough such that even if the design of the random number generator is known, the random numbers generated by the random number generator cannot be predicted. Typically, a random number generator comprises an entropy generator to generate a seed that is then input into a mixing function (e.g., SHA-1, MD5 etc.). However, a large number of random number generators, utilize a deterministic process, i.e., a process whose outcome is predictable, to generate an output from an initial seed. This may be true in the case of most software embodiments of random number generators. Such random number generators, (also called pseudo-random number generators) may be easily compromised, particularly if the seed of the pseudo-random number generator is known or can be predicted.
A true random number generator uses a non-deterministic source, such as, thermal or shot noise associated with a resistor, atmospheric noise, nuclear decay, or some such unpredictable natural process, to generate random numbers. Some random number generators use a natural process, i.e. the thermal or shot noise present when electrons flow through a resistor, radioactive decay, etc. However, the random number generators of these circuits use analog circuitry that may include at least an operation amplifier and a voltage control oscillator. The use of analog circuits in the design of a random number generator makes production of the random number generator difficult. For example, due to the high voltage gain needed to amplify the thermal or shot noise, the output of the operation amplifier could become permanently saturated rendering the random number generator inoperable. In addition, these random number generators may be expensive and may not be portable.
Other random number generators may use a low frequency clocked circuit to sample the output of a linear feedback shift register (LFSR), wherein the LFSR is driven by a higher frequency free running oscillator with a random variation in the frequency to generate random numbers. However, the linear feedback shift register output sequence is inherently periodic, which makes the output of the shift register not truly random, but only pseudo-random. The duration of the period of the LFSR may be increased by using a sufficiently large number of stages in the LFSR. For example, a sixty-four bit linear LFSR running at a clock frequency of one megahertz would not repeat itself for 585,000 years. However, because the LFSR is deterministic, future and past states can be predicted when the present state of an LFSR is known.